package easy

import (
	. "GoLeetcode/common"
	"math"
)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/*
TODO: 还有一种不用hash的方法???
 */

func findMode(root *TreeNode) []int {
	hash := make(map[int]int)
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		hash[node.Val]++
		dfs(node.Left)
		dfs(node.Right)
	}
	dfs(root)

	maxTimesVal := math.MinInt32
	result := make([]int, 0)
	for k, v := range hash {
		if maxTimesVal <= v {
			if maxTimesVal == v {
				result = append(result, k)
			} else {
				result = []int{k}
			}
			maxTimesVal = v
		}
	}
	return result
}
